
package mvcc

import (
	"sort"
	"sync"

	"github.com/google/btree"
	"go.uber.org/zap"
)

type index interface {
	// 查询指定的key
	Get(key []byte, atRev int64) (rev, created revision, ver int64, err error)
	// 范围查询
	Range(key, end []byte, atRev int64) ([][]byte, []revision)
	Revisions(key, end []byte, atRev int64, limit int) ([]revision, int)
	CountRevisions(key, end []byte, atRev int64) int
	// 添加元素
	Put(key []byte, rev revision)
	Tombstone(key []byte, rev revision) error
	RangeSince(key, end []byte, rev int64) []revision
	Compact(rev int64) map[revision]struct{}
	Keep(rev int64) map[revision]struct{}
	Equal(b index) bool

	Insert(ki *keyIndex)
	KeyIndex(ki *keyIndex) *keyIndex
}

type treeIndex struct {
	sync.RWMutex
	tree *btree.BTree
	lg   *zap.Logger
}

// newTreelndex()函数中完成了对tree字段的初始化
func newTreeIndex(lg *zap.Logger) index {
	return &treeIndex{
		// 这里将BTree的度初始化为32'&f除了根节点的每个节点至少有32个元素，每个节点最多有64个元素
		tree: btree.New(32),
		lg:   lg,
	}
}

// treelndex.Put（）方法，其中主要完成两项操作，
// 一是向BTree中添加keyIndex实例，二是向keyIndex中追加revision信息
func (ti *treeIndex) Put(key []byte, rev revision) {
	keyi := &keyIndex{key: key}	// 创建keylndex实例

	ti.Lock()
	defer ti.Unlock()
	// 通过BTree.Get（）方法在BTree上查找指定的元素
	item := ti.tree.Get(keyi)
	if item == nil {	// 在BTree中不存在指定的Key
		// 向keylndex中追加一个rev工sion,
		keyi.put(ti.lg, rev.main, rev.sub)
		// 通过BTree.ReplaceOrinsert （）方法向BTree中添加keylndex实例
		ti.tree.ReplaceOrInsert(keyi)
		return
	}
	// 如果在BTree中查找到该Key对应的元素，则向其中迄加一个revision实例
	okeyi := item.(*keyIndex)
	okeyi.put(ti.lg, rev.main, rev.sub)
}

// trelndex.Get（）方法，该方法负责从BTree中查询revision信息
func (ti *treeIndex) Get(key []byte, atRev int64) (modified, created revision, ver int64, err error) {
	keyi := &keyIndex{key: key}	// 创建keylndex实例
	ti.RLock()
	defer ti.RUnlock()
	// 查询指定Key对应的keylndex实例
	if keyi = ti.keyIndex(keyi); keyi == nil {
		return revision{}, revision{}, 0, ErrRevisionNotFound
	}
	// 在查询到的keylndex实例中，查找对应的revision信息
	return keyi.get(ti.lg, atRev)
}


func (ti *treeIndex) KeyIndex(keyi *keyIndex) *keyIndex {
	ti.RLock()
	defer ti.RUnlock()
	return ti.keyIndex(keyi)
}

// treelndex.keylndex（）方法通过BTree.Get（）方法查询指定的元素，
func (ti *treeIndex) keyIndex(keyi *keyIndex) *keyIndex {
	if item := ti.tree.Get(keyi); item != nil {
		return item.(*keyIndex)
	}
	return nil
}

func (ti *treeIndex) visit(key, end []byte, f func(ki *keyIndex) bool) {
	keyi, endi := &keyIndex{key: key}, &keyIndex{key: end}

	ti.RLock()
	defer ti.RUnlock()

	ti.tree.AscendGreaterOrEqual(keyi, func(item btree.Item) bool {
		if len(endi.key) > 0 && !item.Less(endi) {
			return false
		}
		if !f(item.(*keyIndex)) {
			return false
		}
		return true
	})
}

func (ti *treeIndex) Revisions(key, end []byte, atRev int64, limit int) (revs []revision, total int) {
	if end == nil {
		rev, _, _, err := ti.Get(key, atRev)
		if err != nil {
			return nil, 0
		}
		return []revision{rev}, 1
	}
	ti.visit(key, end, func(ki *keyIndex) bool {
		if rev, _, _, err := ki.get(ti.lg, atRev); err == nil {
			if limit <= 0 || len(revs) < limit {
				revs = append(revs, rev)
			}
			total++
		}
		return true
	})
	return revs, total
}

func (ti *treeIndex) CountRevisions(key, end []byte, atRev int64) int {
	if end == nil {
		_, _, _, err := ti.Get(key, atRev)
		if err != nil {
			return 0
		}
		return 1
	}
	total := 0
	ti.visit(key, end, func(ki *keyIndex) bool {
		if _, _, _, err := ki.get(ti.lg, atRev); err == nil {
			total++
		}
		return true
	})
	return total
}

// Range（）方法，该方法负责查询BTree中key~end之间元素中指定revision信息
func (ti *treeIndex) Range(key, end []byte, atRev int64) (keys [][]byte, revs []revision) {
	if end == nil {
		// 如果未指定end参数，Ji!1J只查询key对应的revision信息，
		rev, _, _, err := ti.Get(key, atRev)
		if err != nil {
			return nil, nil
		}
		return [][]byte{key}, []revision{rev}
	}
	ti.visit(key, end, func(ki *keyIndex) bool {
		// 从当前元素中查询指定的revision元素，并追加到revs中
		if rev, _, _, err := ki.get(ti.lg, atRev); err == nil {
			revs = append(revs, rev)
			// 将当前key追加到keys中，等待返回
			keys = append(keys, ki.key)
		}
		return true
	})
	return keys, revs
}

// treelndex.Tombstone（）方法，该方法会先在BTree中查找指定的key Index实例，
// 然后调用keyIndex. tombstone（）方法结束其当前generation实例井创建新的generation实例。
func (ti *treeIndex) Tombstone(key []byte, rev revision) error {
	keyi := &keyIndex{key: key}

	ti.Lock()
	defer ti.Unlock()
	item := ti.tree.Get(keyi)
	if item == nil {
		return ErrRevisionNotFound
	}

	ki := item.(*keyIndex)
	return ki.tombstone(ti.lg, rev.main, rev.sub)
}

// treelndex.RangeSince（）方法，该方法会查询了key～end的元素，
// 并从中查询main revision部分大于指定值的revision信息。注意，
// 最终返回的revision实例不是按照key进行排序的，而是按照revision.GreaterThan（）排序的。
func (ti *treeIndex) RangeSince(key, end []byte, rev int64) []revision {
	// 创建key对反的keyIndex实例
	keyi := &keyIndex{key: key}
	// 加锁和解锁的相关逻辑
	ti.RLock()
	defer ti.RUnlock()

	if end == nil {
		// 如果未指定end参数，则只查询key对应的revision信息
		item := ti.tree.Get(keyi)
		if item == nil {
			return nil
		}
		keyi = item.(*keyIndex)
		// 调用keyIndex.since（）方法，获取rev之后的revision实例，
		return keyi.since(ti.lg, rev)
	}

	endi := &keyIndex{key: end}
	var revs []revision
	// 调用BTree.AscendGreaterOrEqual（）方法追历比key大的元素
	ti.tree.AscendGreaterOrEqual(keyi, func(item btree.Item) bool {
		if len(endi.key) > 0 && !item.Less(endi) {	// 忽略大于end的元素
			return false
		}
		curKeyi := item.(*keyIndex)
		// 调用keyindex.since（）方法，获取当前keyindex实例中rev之后的revision实例
		revs = append(revs, curKeyi.since(ti.lg, rev)...)
		return true
	})
	// 对revs中记录的revision实例进行排序，并返回
	sort.Sort(revisions(revs))
	return revs
}

// treeIndex. Compact（）方法，其中会遍历BTree中所有的keyIndex实例，
// 并调用keyIndex.compact（）方法对其中的generations进行压缩
func (ti *treeIndex) Compact(rev int64) map[revision]struct{} {
	available := make(map[revision]struct{})
	ti.lg.Info("compact tree index", zap.Int64("revision", rev))
	ti.Lock()
	clone := ti.tree.Clone()
	ti.Unlock()
	// Ascend（）方法运历其中的全部keyindex实例，在远历过程中，
	// 会将待删除的keyIndex实例添加圭1Jemptyki中
	clone.Ascend(func(item btree.Item) bool {
		keyi := item.(*keyIndex)
		// 此处需要锁定，以防止在
		// 压缩正在进行或删除前将修订添加为空
		ti.Lock()
		keyi.compact(ti.lg, rev, available)
		if keyi.isEmpty() {
			item := ti.tree.Delete(keyi)
			if item == nil {
				ti.lg.Panic("failed to delete during compaction")
			}
		}
		ti.Unlock()
		return true
	})
	return available
}

// Keep查找要保留的所有修订，以便以给定的修订进行压缩。
func (ti *treeIndex) Keep(rev int64) map[revision]struct{} {
	available := make(map[revision]struct{})
	ti.RLock()
	defer ti.RUnlock()
	ti.tree.Ascend(func(i btree.Item) bool {
		keyi := i.(*keyIndex)
		keyi.keep(rev, available)
		return true
	})
	return available
}

func (ti *treeIndex) Equal(bi index) bool {
	b := bi.(*treeIndex)

	if ti.tree.Len() != b.tree.Len() {
		return false
	}

	equal := true

	ti.tree.Ascend(func(item btree.Item) bool {
		aki := item.(*keyIndex)
		bki := b.tree.Get(item).(*keyIndex)
		if !aki.equal(bki) {
			equal = false
			return false
		}
		return true
	})

	return equal
}

// Insert（）方法，它直接调用BTree.ReplaceOrlnsert（）方法插入keyIndex 实例
func (ti *treeIndex) Insert(ki *keyIndex) {
	ti.Lock()
	defer ti.Unlock()
	ti.tree.ReplaceOrInsert(ki)
}
